package com.its.system.algotithm.class07;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/*
  * 	加强堆
  * 	手动改写堆的代码讲解
  * 	1）建立反向索引表
		2）建立比较器
		3）核心在于各种结构相互配合，非常容易出错
 * T一定要是非基础类型，有基础类型需求包一层
 */
public class HeapGreater<T> {
    /**
     * 封装基础数据类型
     * @param <T>
     */
    class Inner<T> {
        public T value;

        public Inner(T v) {
            value = v;
        }
    }

    /*数组 set更新 和 get O1*/
    private ArrayList<T> heap;

    /*
    反向索引表
    对象存放的位置
    eg:[a,b,c]
    a->0
    b->1
    c->2
     */
    private HashMap<T, Integer> indexMap;
    /*堆的大小 数组*/
    private int heapSize;
    /* 两个对象如何比大小 比较器 */
    private Comparator<? super T> comp;

    /**
     * 构造器 初始化
     * @param c
     */
    public HeapGreater(Comparator<? super T> c) {
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        comp = c;
    }

    /**
     * 空判断
     * @return
     */
    public boolean isEmpty() {
        return heapSize == 0;
    }

    /**
     * 堆大小
     * @return
     */
    public int size() {
        return heapSize;
    }

    /**
     * 是否包含对象 反向索引表查询
     * @param obj
     * @return
     */
    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    /**
     * 堆顶 取出 不弹出
     * @return
     */
    public T peek() {
        return heap.get(0);
    }

    /**
     * 添加一个元素  注意反向索引表 基础数据类型的覆盖问题
     * @param obj
     */
    public void push(T obj) {
        //堆中添加
        heap.add(obj);
        //反向索引表
        indexMap.put(obj, heapSize);
        //调整堆   元素调整 对应的indexMap也需要调整
        heapInsert(heapSize++);
    }

    /**
     * 弹出
     * @return
     */
    public T pop() {
        T ans = heap.get(0);
        //最后位置 与0 位置
        swap(0, heapSize - 1);

        indexMap.remove(ans);
        heap.remove(--heapSize);
        //向下堆调整
        heapify(0);
        return ans;
    }

    /**
     * 高效的 删除
     * @param obj
     */
    public void remove(T obj) {
        T replace = heap.get(heapSize - 1);
        int index = indexMap.get(obj);
        indexMap.remove(obj);
        heap.remove(--heapSize);
        if (obj != replace) {
            heap.set(index, replace);
            indexMap.put(replace, index);
            resign(replace);
        }
    }

    /**
     * 给定对象 调整堆
     * @param obj
     */
    public void resign(T obj) {
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }

    // 请返回堆上的所有元素
    public List<T> getAllElements() {
        List<T> ans = new ArrayList<>();
        for (T c : heap) {
            ans.add(c);
        }
        return ans;
    }

    /**
     * 堆调整
     * @param index
     */
    private void heapInsert(int index) {
        //heap.get(index) 当前添加位置
        //父位置   heap.get((index - 1) / 2)
        //比较 两个数 根据比较器比大小
        while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            //交换
            swap(index, (index - 1) / 2);
            //当前位置等于 父位置
            index = (index - 1) / 2;
        }
    }

    private void heapify(int index) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int best = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
            best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
            if (best == index) {
                break;
            }
            swap(best, index);
            index = best;
            left = index * 2 + 1;
        }
    }

    /**
     * 两个元素的调整 同时调整 indexMap
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        heap.set(i, o2);
        heap.set(j, o1);
        indexMap.put(o2, i);
        indexMap.put(o1, j);
    }

}
